Rotate List

LeetCode 61 | Difficulty: Medium

Medium

Problem Description

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

- The number of nodes in the list is in the range `[0, 500]`.

- `-100 <= Node.val <= 100`

- `0 <= k <= 2 * 10^9`

Topics: Linked List, Two Pointers

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 162 ms)

Metric	Value
Runtime	162 ms
Memory	N/A
Date	2017-09-19

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if(head==null || head.next == null) return head;
        ListNode tail = head, current = head;
        int length = 1;
        while (tail.next != null)
        {
            length++;
            tail = tail.next;
        }
        k = k % length;
        if(k==0) return head;
        for (int i = 0; i < length-k-1; i++)
        {
            current = current.next;
        }
        
        var newHead = current.next;
        tail.next = head;
        current.next = null;
        return newHead;
    }
}

📜 1 more C# submission(s)

Submission (2017-09-19) — 162 ms, N/A

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if(head==null || head.next == null) return head;
        ListNode temp = head;
        ListNode slow = head, fast = head;
        int length = 0;
        while (slow != null)
        {
            length++; slow = slow.next;
        }
        k = k % length;
        if(k==0) return head;
        slow = temp;
        for (int i = 0; i < k; i++)
        {
            fast = fast.next;
        }
        while (fast.next != null)
        {
            slow = slow.next;
            fast = fast.next;
        }
//      slow.Dump("slow");
//      fast.Dump("fast");
//      temp.Dump("temp");
        var newHead = slow.next;
        fast.next = temp;
        slow.next = null;
        fast = temp;
        return newHead;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.